package top.minuy.structure.tree.bst;

import top.minuy.structure.queue.LinkedListQueue;
import top.minuy.structure.stack.LinkedListStack;

/**
 * 二分搜索树
 *
 * @author Minuy
 * @time 17:38
 * @date 2021/9/9
 * @param <E> 泛型支持 可比较类型
 */
public class BST<E extends Comparable<E>> {
    /**
     * 二叉树节点
     */
    class Node {
        // 元素
        public E e;
        // 左右节点
        public Node left, right;

        public Node(E e) {
            this(e, null, null);
        }

        public Node(E e, Node left, Node right) {
            this.e = e;
            this.left = left;
            this.right = right;
        }
    }

    // 根节点
    private Node root;
    // 大小
    private int size;

    /**
     * 创建一个二分搜索树
     */
    public BST() {
        root = null;
        size = 0;
    }

    /**
     * 获取树大小
     *
     * @return 树的大小
     */
    public int size() {
        return size;
    }

    /**
     * 判断树是否为空
     *
     * @return 是否为空树
     */
    public boolean isEmpty() {
        return size == 0;
    }


    public void remove(E e){
        root = remove(root ,e);
    }

    private Node remove(Node node,E e) {
        if(node == null){
            return null;
        }

        if(e.compareTo(node.e)>0){
            node.right = remove(node.right,e);
            return node;
        }else if (e.compareTo(node.e)<0){
            node.left = remove(node.left,e);
            return node;
        }else { // e == node.e

            if(node.left == null){
                Node t = node.right;
                node.right = null;
                size--;
                return t;
            }

            if(node.right == null){
                Node t = node.left;
                node.left = null;
                size--;
                return t;
            }

            /*
            Node precursor = maximum(node.left);  // 找出前驱

            // 注意这里要“保存修改”
            node.left = removeMax(node.left);  // 在原来的树中删除前驱

            precursor.left = node.left;  // 前驱替代当前节点
            precursor.right = node.right;  // 前驱替代当前节点

            node.right=node.left=null;  // 断开当前节点的连接

            return precursor;  // 前驱作为根节点返回

             */

            Node successor = minimum(node.right);  // 找出后继

            node.right = removeMin(node.right);   // 把后继脱离出当前的树(这里size已经-1了)

            successor.right = node.right;  // 后继替代当前节点
            successor.left = node.left;  // 后继替代当前节点

            node.right=node.left = null;  // 当前节点断开连接

            return successor;
        }
    }


    public E maximum() {
        if (root != null) {
            return maximum(root).e;
        }else {
            throw new IllegalArgumentException("Maximum failed. BST is Empty.");
        }
    }

    private Node maximum(Node node){
        if(node.right==null){
            return node;
        }
        return maximum(node.right);
    }

    public E removeMax(){
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

    /**
     * 删除最小值
     * @param node 要删除最小值的根结点
     * @return 根结点
     */
    private Node removeMax(Node node){
        if(node.right!=null){
            node.right = removeMax(node.right);
            return node;
        }else {
            size--;
            Node t = node.left;
            node.left = null;
            return t;
        }
    }

    public E minimum() {
        if (root != null) {
            return minimum(root).e;
        }else {
            throw new IllegalArgumentException("Minimum failed. BST is Empty.");
        }
    }

    private Node minimum(Node node){
        if(node.left==null){
            return node;
        }
        return minimum(node.left);
    }

    public E removeMin(){
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    /**
     * 删除最大值
     * @param node 要删除最大值的根节点
     * @return 根节点
     */
    private Node removeMin(Node node){
        if(node.left!=null){
            node.left = removeMax(node.left);
            return node;
        }else {
            size--;
            Node t = node.right;
            node.right = null;
            return t;
        }
    }

    /*
        public void add(E e){
            add(root,e);
        }

        private void add(Node node,E e){
            if(node == null){
                node = new Node(e);
                size++;
            }else if(e.compareTo(node.e)>0){
                add(node.right,e);
                size++;
            }else if (e.compareTo(node.e)<0){
                add(node.left,e);
                size++;
            }
        }
     */
    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
            // 这里并没有新增任何元素
            //size++;
        } else if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
            // 这里并没有新增任何元素
            //size++;
        }

        // 满足有返回值语法
        return node;
    }

    /**
     * 查找元素是否存在二分搜索树中
     *
     * @param e 要搜索的元素
     * @return 是否存在
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }

        if (e.compareTo(node.e) == 0) {
            return true;
        }
        /*
        boolean left = false,right = false;
        if(node.left!=null){
             left = contains(node.left,e);
        }
        if (node.right!=null){
            right = contains(node.right,e);
        }
        return left || right;

         */
        if (e.compareTo(node.e) < 0) {
            // 小于节点，到左边去找
            return contains(node.left, e);
        } else {
            // 大于节点，到右边去找
            return contains(node.right, e);
        }
    }

    /**
     * 广度优先遍历，非递归实现
     */
    public void levenOrder(){
        // 使用队列辅助完成
        LinkedListQueue<Node> queue = new LinkedListQueue<>();
        // 如果根节点不为空，入队
        if(root!=null){
            queue.enqueue(root);
        }
        // 如果队列内不为空，继续遍历
        while (!queue.isEmpty()){
            // 从队列中取出一个元素
            Node cur = queue.dequeue();
            // 访问
            System.out.print(cur.e+" ");
            // 左节点先入队（左节点先处理）
            if(cur.left!=null){
                queue.enqueue(cur.left);
            }
            // 右节点入队
            if(cur.right!=null){
                queue.enqueue(cur.right);
            }
        }

    }

    /**
     * 非递归实现前序遍历
     */
    public void preOrderNr(){
        // 使用栈来记录访问节点
        LinkedListStack<Node> stack = new LinkedListStack<>();

        // 访问根节点
        if(root!=null) {
            stack.push(root);
        }

        // 如果栈不为空，继续访问
        while (!stack.isEmpty()){
            // 出栈
            Node cur = stack.pop();
            // 访问
            System.out.print(cur.e+" ");

            // 先压右边的，这个后面访问
            if(cur.right!=null){
                stack.push(cur.right);
            }

            // 再压左边的元素入栈
            if(cur.left!=null){
                stack.push(cur.left);
            }
        }
    }

    public void preOrder(){
        preOrder(root);
    }

    public void inOrder(){
        inOrder(root);
    }
    public void postOrder() {
        postOrder(root);
    }
    private void postOrder(Node node){
        if(node == null){
            return;
        }

        postOrder(node.left);

        postOrder(node.right);

        System.out.print(node.e+" ");
    }

    private void inOrder(Node node){
        if(node == null){
            return;
        }

        inOrder(node.left);

        System.out.print(node.e+" ");

        inOrder(node.right);
    }

    private void preOrder(Node node){
        if(node==null){
            return;
        }
        System.out.print(node.e+" ");

        preOrder(node.left);

        preOrder(node.right);

    }

    public void addNr(E e) {

        if(root == null){
            // 头结点这里不要忘了维护size
            size++;
            root = new Node(e);
            return;
        }

        Node tagNode = root;
        while (true) {
            if (e.compareTo(tagNode.e) < 0) {
                // 到左节点去
                if (tagNode.left == null) {
                    tagNode.left = new Node(e);
                    size++;
                    return;
                }
                tagNode = tagNode.left;
            } else if (e.compareTo(tagNode.e) > 0) {
                // 到右节点去
                if (tagNode.right == null) {
                    tagNode.right = new Node(e);
                    size++;
                    return;
                }
                tagNode = tagNode.right;
            } else {
                // 遇到相等的，直接不用再添加了
                return;
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root,0,res);
        return res.toString();
    }

    /**
     * 生成二分搜索树的字符串
     * @param node 二分搜索树的根节点
     * @param depth 当前深度
     * @param res 字符串构建对象
     */
    private void generateBSTString(Node node, int depth, StringBuilder res) {
        generateDepthString(depth,res);
        if(node == null){
            res.append("null");
            res.append("\n");
        }else {
            res.append(node.e.toString());
            res.append("\n");

            generateBSTString(node.left,depth+1,res);
            generateBSTString(node.right,depth+1,res);
        }
    }

    /**
     * 生成树层次长度
     * @param depth 层次
     * @param res 字符串构造器
     */
    private void generateDepthString(int depth, StringBuilder res) {
        for (int i=0;i<depth;i++){
            res.append("-|");
        }
    }
}

// 备复制的最小实现
//
//public class RBTree<E extends Comparable<E>> {
//    /**
//     * 二叉树节点
//     */
//    class Node {
//        // 元素
//        public E e;
//        // 左右节点
//        public Node left, right;
//
//        public Node(E e) {
//            this(e, null, null);
//        }
//
//        public Node(E e, Node left, Node right) {
//            this.e = e;
//            this.left = left;
//            this.right = right;
//        }
//    }
//
//    // 根节点
//    private Node root;
//    // 大小
//    private int size;
//
//    /**
//     * 创建一个二分搜索树
//     */
//    public RBTree() {
//        root = null;
//        size = 0;
//    }
//
//    /**
//     * 获取树大小
//     *
//     * @return 树的大小
//     */
//    public int size() {
//        return size;
//    }
//
//    /**
//     * 判断树是否为空
//     *
//     * @return 是否为空树
//     */
//    public boolean isEmpty() {
//        return size == 0;
//    }
//
//    /**
//     * 删除一个元素
//     * @param e 要删除的元素
//     */
//    public void remove(E e) {
//        root = remove(root, e);
//    }
//
//    /**
//     * 删除元素的递归算法
//     * @param node 删除元素的根节点
//     * @param e 要删除的元素
//     * @return 被删除元素后的子树
//     */
//    private Node remove(Node node, E e) {
//        if (node == null) {
//            return null;
//        }
//
//        if (e.compareTo(node.e) > 0) {
//            node.right = remove(node.right, e);
//            return node;
//        } else if (e.compareTo(node.e) < 0) {
//            node.left = remove(node.left, e);
//            return node;
//        } else { // e == node.e
//            if (node.left == null) {
//                Node t = node.right;
//                node.right = null;
//                size--;
//                return t;
//            }
//
//            if (node.right == null) {
//                Node t = node.left;
//                node.left = null;
//                size--;
//                return t;
//            }
//
//            Node successor = minimum(node.right);  // 找出后继
//
//            node.right = remove(node.right, successor.e);   // 把后继脱离出当前的树(这里size已经-1了)
//
//            successor.right = node.right;  // 后继替代当前节点
//            successor.left = node.left;  // 后继替代当前节点
//
//            node.right = node.left = null;  // 当前节点断开连接
//
//            return successor;
//        }
//    }
//
//    /**
//     * 找出本棵树中的最小值
//     * @param node 树的根节点
//     * @return 本棵树中值的最小的节点
//     */
//    private Node minimum(Node node) {
//        if (node.left == null) {
//            return node;
//        }
//        return minimum(node.left);
//    }
//
//    /**
//     * 添加一个元素到树中
//     * @param e 要添加的元素
//     */
//    public void add(E e) {
//        root = add(root, e);
//    }
//
//    /**
//     * 添加元素的递归
//     * @param node 要添加到的树的根结点
//     * @param e 要添加的元素
//     * @return 添加元素后树的根结点
//     */
//    private Node add(Node node, E e) {
//        if (node == null) {
//            size++;
//            return new Node(e);
//        } else if (e.compareTo(node.e) > 0) {
//            node.right = add(node.right, e);
//        } else if (e.compareTo(node.e) < 0) {
//            node.left = add(node.left, e);
//        }
//        return node;
//    }
//
//    /**
//     * 查找元素是否存在二分搜索树中
//     *
//     * @param e 要搜索的元素
//     * @return 是否存在
//     */
//    public boolean contains(E e) {
//        return contains(root, e);
//    }
//
//    /**
//     * 查找的递归算法
//     * @param node 要查找的根结点
//     * @param e 要查找的元素
//     * @return 是否存在要查找的元素
//     */
//    private boolean contains(Node node, E e) {
//        if (node == null) {
//            return false;
//        }
//
//        if (e.compareTo(node.e) == 0) {
//            return true;
//        }
//        if (e.compareTo(node.e) < 0) {
//            // 小于节点，到左边去找
//            return contains(node.left, e);
//        } else {
//            // 大于节点，到右边去找
//            return contains(node.right, e);
//        }
//    }
//
//    @Override
//    public String toString() {
//        StringBuilder res = new StringBuilder();
//        generateBSTString(root, 0, res);
//        return res.toString();
//    }
//
//    /**
//     * 生成二分搜索树的字符串
//     *
//     * @param node  二分搜索树的根节点
//     * @param depth 当前深度
//     * @param res   字符串构建对象
//     */
//    private void generateBSTString(Node node, int depth, StringBuilder res) {
//        generateDepthString(depth, res);
//        if (node == null) {
//            res.append("null");
//            res.append("\n");
//        } else {
//            res.append(node.e.toString());
//            res.append("\n");
//
//            generateBSTString(node.left, depth + 1, res);
//            generateBSTString(node.right, depth + 1, res);
//        }
//    }
//
//    /**
//     * 生成树层次长度
//     *
//     * @param depth 层次
//     * @param res   字符串构造器
//     */
//    private void generateDepthString(int depth, StringBuilder res) {
//        for (int i = 0; i < depth; i++) {
//            res.append("-|");
//        }
//    }
//}

